package EurekaProcessor;

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Vector;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.*;

import Config.Configure;
import Config.GlobalLog;
import EurekaAnalyzer.IDInformation;
import Statistics.IDGraph;
import Statistics.IDGraphGlobalProperty;
import Statistics.IDGraphNode;
import Statistics.IDGraphToJungGraph;
import Store.StoreManager;

public class Clusterer {
	public static class Record
	{
		public int a, b;
		public float sim;
		Record(int _a, int _b, float _sim)
		{
			a = _a;
			b = _b;
			sim = _sim;
		}
	}
	
	static int p[];
	
	public static class SortBySim implements Comparator<Record>{
		@Override
		public int compare(Record left, Record right) {
			if(left.sim >right.sim)
				return -1;
			else
				return 1;
		}
	}
	
	public static int cc = 0;
	public static Set<Set<String>> HierarchicalClustering(IDGraph graph, int stop)
	{
		Set<Set<String>> clusters = new HashSet<Set<String>>();
		//Init clusters - Make every node a single cluster
		List<String> nodes = new ArrayList<String>(graph.GetNodeMap().keySet());
		int n = 0;
		for(int i = 0; i < nodes.size(); i++)
		{
			Set<String> singleCluster = new HashSet<String>();
			singleCluster.add(nodes.get(i));
			int degree = graph.GetNodeMap().get(nodes.get(i)).GetInDegree() + graph.GetNodeMap().get(nodes.get(i)).GetOutDegree();
			if(degree != 0)
			{
				n++;
				clusters.add(singleCluster);
			}
		}
		System.out.println("Total Nodes: " + n);
		
		for(int step = 1; step < n - stop; step++)
		{
			System.out.println("Step: " + step);
			//Find the nearest pair of clusters a, b
			Set<String> a = null, b = null;
			List<Set<String>> clusterList = new ArrayList<Set<String>>(clusters);
			float max = -1;
			cc = 0;
			int clusize = clusterList.size();
			for(int i = 0; i < clusize; i++)
				for(int j = i+1; j < clusize; j++)
				{
					float sim = clusterSimilarity(clusterList.get(i), clusterList.get(j), graph);
					if(sim > max)
					{
						max = sim;
						a = clusterList.get(i);
						b = clusterList.get(j);
					}
				}
			//Combine a b
			clusters.remove(a);
			clusters.remove(b);
			a.addAll(b);
			clusters.add(a);
			System.out.println("cc = " + cc);
		}
		
		return clusters;
	}
	
	public static float clusterSimilarity(Set<String> a, Set<String> b, IDGraph graph)
	{
		float max = -1;
		List<String> aList = new ArrayList<String>(a);
		List<String> bList = new ArrayList<String>(b);
		cc += aList.size() + bList.size();
		int asize = aList.size();
		int bsize = bList.size();
		for(int i = 0; i < asize; i++)
			for(int j = 0; j < bsize; j++)
			{
				float sim = nodeSimilarity(aList.get(i), bList.get(j), graph);
				if(sim > max)
					max = sim;
			}
					
		return max;
	}
	
	public static float nodeSimilarity(String a, String b, IDGraph graph)
	{
		float sim = 0;
		int count = 0;
		
		IDGraphNode aNode = graph.GetNodeMap().get(a);
		IDGraphNode bNode = graph.GetNodeMap().get(b);
		Set<String> aNeighbors = new HashSet<String>();
		Set<String> bNeighbors = new HashSet<String>();
		aNeighbors.addAll(aNode.GetInEdges().keySet());
		aNeighbors.addAll(aNode.GetOutEdges().keySet());
		bNeighbors.addAll(bNode.GetInEdges().keySet());
		bNeighbors.addAll(bNode.GetOutEdges().keySet());
		
		//System.out.println(aNeighbors.size() + bNeighbors.size());
		
		List<String> bNeighborsList = new ArrayList<String>(bNeighbors);
		List<String> aNeighborsList = new ArrayList<String>(aNeighbors);
		
		int bsize = bNeighborsList.size();
		for(int i = 0; i < bsize; i++)
			if(aNeighbors.contains(bNeighborsList.get(i)))
				count++;
		if(aNeighbors.contains(bNode.GetID()))
			count++;
		if(bNeighbors.contains(aNode.GetID()))
			count++;
		sim = new Float(count); /// (aNeighbors.size() + bNeighbors.size() + 2);
/*		
		System.out.println(a + " " + b + ":" + sim);
		System.out.print("aNei:");
		for(int i = 0; i < aNeighborsList.size(); i++)
			System.out.print(aNeighborsList.get(i) + " ");
		System.out.println();
		System.out.print("bNei:");
		for(int i = 0; i < bNeighborsList.size(); i++)
			System.out.print(bNeighborsList.get(i) + " ");
		System.out.println();
*/		
		
		
		return sim;
	}
	
	public static int FindC(int x)
	{
		if(p[x] == -1)
			return x;
		else
			return FindC(p[x]);
	}
	
	public static Set<Set<String>> HierarchicalClusteringFast(IDGraph graph, int stop)
	{
		Set<Set<String>> clusters = new HashSet<Set<String>>();
		List<Set<String>> clusterList = new ArrayList<Set<String>>();
		//Init clusters - Make every node a single cluster
		List<String> nodes = new ArrayList<String>(graph.GetNodeMap().keySet());
		String node[] = new String[6500];
		int n = 0;
		for(int i = 0; i < nodes.size(); i++)
		{
			Set<String> singleCluster = new HashSet<String>();
			singleCluster.add(nodes.get(i));
			int degree = graph.GetNodeMap().get(nodes.get(i)).GetInDegree() + graph.GetNodeMap().get(nodes.get(i)).GetOutDegree();
			if(degree != 0)
			{
				node[n] = nodes.get(i);
				n++;
				clusterList.add(singleCluster);
			}
		}
		System.out.println("Total Nodes: " + n);
		
		List<Record> rec = new ArrayList<Record>();
		int m = 0;
		for(int i = 0; i < n; i++)
			for(int j = i+1; j < n; j++)
			{
				float sim = nodeSimilarity(node[i], node[j], graph);
				rec.add(new Record(i, j, sim));
				m++;
				if(node[i].equals("KMZ") && sim > 0.00001)
				{
					System.out.println(node[i] + " " + node[j] + " " + sim);
				}
			}
		SortBySim sbs = new SortBySim();
		Collections.sort(rec, sbs);
		p = new int[n];
		for(int i = 0; i < n; i++)
			p[i] = -1;
		
/*
		for(int i = 0; i < rec.size(); i++)
			if(rec.get(i).sim > 0)
				System.out.println(node[rec.get(i).a] + " " + node[rec.get(i).b] + " " + rec.get(i).sim);
*/			
		int step = 0;
		int nc = n;
		int size = rec.size();
		while(nc > stop && step < size)
		{
			float sim = rec.get(step).sim;
			if(sim < 0.0001)
				break;
//			System.out.println("Step: " + step);
			int a = rec.get(step).a;
			int b = rec.get(step).b;
			int ca = FindC(a);
			int cb = FindC(b);
			if(ca != cb)
			{
				p[ca] = cb;
				nc--;
			}
			if(node[a].equals("KMZ") || node[b].equals("KMZ"))
				System.out.println(node[a] + " " + node[a] + " " + sim);
			step++;
		}
		System.out.println("size =" + rec.size());
		
		//merge
		for(int i = 0; i < n; i++)
		{
			int c = FindC(i);
			if(node[i].equals("KMZ"))
			{
				System.out.println("KMZ=node[" + i + "]");
				System.out.println(p[i]);
			}
			if(node[c].equals("KMZ"))
			{
				System.out.println("KMZ+=node[" + i + "]");
				System.out.println(node[i]);
			}
			if(c != i)
			{
				clusterList.get(c).add(node[i]);
			}
		}
		
		//gather
		for(int i = 0; i < n; i++)
		{
			int c = FindC(i);
			if(c == i)
			{
				clusters.add(clusterList.get(c));
			}
		}
		
		return clusters;
	}
}
